package week_2;
//494.
public class day01_week02 {

    public static void main(String[] args) {

        int[] nums=new int[]{1,1,1,1,1};
        int target=3;
        System.out.println(findTargetSumWays(nums,target));
    }
    /*
    方法一:回溯
     */
    //声明一个全局量
    static int count=0;
    /**
     * 调用一个回溯方法
     * 本质上是遍历枚举
     * 把所有的可能列出来并判断结果
     * @param nums
     * @param target
     * @return
     */
    public static int findTargetSumWays(int[] nums, int target) {
        //回溯方法
        backtrack(nums,target,0,0);
        return count;
    }

    /**
     *
     * @param nums
     * @param target
     * @param length 0
     * @param size 0
     */
    private static void backtrack(int[] nums, int target,int length,int size) {
        //判断是否满足一下要求
            //1.已经为数组所有的元素打上了'+','-'标记(已经没有元素的状态为未知)
            //2.运算结果符合要求
        if(length==nums.length){
            if (size==target){
                count++;
            }
        }else {
            //为数组的下一位添加符号
            backtrack(nums, target, length+1, size+nums[length]);
            backtrack(nums, target, length+1, size-nums[length]);
        }
    }
}
